|
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings.〔.〕 The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are. The classical integer sorting algorithms of bucket sort, counting sort, and radix sort are widely used and practical.〔; .〕 Much of the subsequent research on integer sorting algorithms has focused less on practicality and more on theoretical improvements in their worst case analysis, and the algorithms that come from this line of research are not believed to be practical for current 64-bit computer architectures, although experiments have shown that some of these methods may be an improvement on radix sorting for data with 128 or more bits per key.〔.〕 Additionally, for large data sets, the near-random memory access patterns of many integer sorting algorithms can handicap them compared to comparison sorting algorithms that have been designed with the memory hierarchy in mind.〔.〕 Integer sorting provides one of the six benchmarks in the DARPA High Productivity Computing Systems Discrete Mathematics benchmark suite,〔(DARPA HPCS Discrete Mathematics Benchmarks ), Duncan A. Buell, University of South Carolina, retrieved 2011-04-20.〕 and one of eleven benchmarks in the NAS Parallel Benchmarks suite. ==Models of computation== Time bounds for integer sorting algorithms typically depend on three parameters: the number of data values to be sorted, the magnitude of the largest possible key to be sorted, and the number of bits that can be represented in a single machine word of the computer on which the algorithm is to be performed. Typically, it is assumed that ; that is, that machine words are large enough to represent an index into the sequence of input data and that they are large enough to represent a single key.〔.〕 Integer sorting algorithms are usually designed to work in either the pointer machine or random access machine models of computing; the main difference between these two models is that the random access machine allows any value that is stored in a register to be used as the address of memory read and write operations, with unit cost per operation, allowing certain complex operations on data to be implemented quickly using table lookups. In contrast, the pointer machine model allows memory access only via pointers to memory that may not be manipulated using arithmetic operations. In both models, addition, bitwise Boolean operations, and binary shift operations may typically also be accomplished in unit time per operation. Different integer sorting algorithms make different assumptions, however, about whether integer multiplication is also allowed as a unit-time operation.〔The question of whether integer multiplication or table lookup operations should be permitted goes back to ; see also .〕 Other more specialized models of computation such as the parallel random access machine have also been considered.〔; comment in ; ; ; .〕 showed that in some cases the multiplications or table lookups required by some integer sorting algorithms could be replaced by customized operations that would be more easily implemented in hardware but that are not typically available on general-purpose computers; improved this by showing how to replace these operations by the bit-field manipulation instructions available on Pentium processors. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Integer sorting」の詳細全文を読む スポンサード リンク
|